class Solution(object):
    def videoStitching(self, clips, T):  #cips数组用于存储视频片段[i,j]
        #dp[i] 是能覆盖完整视频片段[0,i]的最小所需子视频片段数
        dp =[float('inf')]*(T+1) 
        dp[0] = 0  #初始化
        for i in range(1,T+1):
            for clip in clips:
                # 找到包含结束端点的视频片段
                if (clip[0] < i <= clip[1]):
                    # 缩小问题范围，求覆盖 (0 - clip[0]) 区间的视频的最小片段数量
                    print(dp[i]) 
                    dp[i] = min(dp[i],dp[ clip[0] ] + 1) 
                    # print(dp[i])
                    # print(clip)
                    # print("$$$")
            # print(" ")   
        return -1 if (dp[T] == float('inf')) else dp[T]


clips=[[0,1],[6,8],[0,2],[5,6],[0,4],[0,3],[6,7],[1,3],[4,7],[1,4],[2,5],[2,6],[3,4],[4,5],[5,7],[6,9]]
T=9
s=Solution()
print(s.videoStitching(clips,T))